package violentRecursion;

import org.junit.Test;

import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * @author kunkun
 * @className LeetCode_139
 * @Description 最长递增子序列
 * @date 2025/3/13 17:50
 */
public class LeetCode_300 {
    public int lengthOfLIS(int[] nums) {
//        return solution_1(nums,0,null);
        finalRes =new Integer[nums.length][nums.length+1];
        return solution_2(nums,0,-1);
//        return solution_3(nums);

    }

    @Test
    public void test(){
        System.out.println(lengthOfLIS(new int[]{10,9,2,5,3,7,101,18}));//4
    }

    //递归
    private int solution_1(int[] nums,int index,Integer before) {
        //1. 条件
        if (index==nums.length){
            return 0;
        }
        //2. 递归
        int result1,result2;
        if (before==null||nums[index]>before){
            result1=solution_1(nums,index+1,nums[index])+1; //携带
            result2=solution_1(nums,index+1,before);    //不携带
            return Math.max(result1,result2);
        }else {
            return solution_1(nums,index+1,before);
        }
    }

    //严格表
    private Integer[][] finalRes;
    private int solution_2(int[] nums,int index,Integer preIndex) {
        if (index==nums.length){
            return 0;
        }
        if (finalRes[index][preIndex+1]!=null){
            return finalRes[index][preIndex+1];
        }

        //2. 递归
        int result1,result2;
        if (preIndex==-1||nums[index]>nums[preIndex]){
            result1=solution_2(nums,index+1,index)+1; //携带
            result2=solution_2(nums,index+1,preIndex);    //不携带
            int result =Math.max(result1,result2);
            finalRes[index][preIndex+1]=result;
            return result;
        }else {
            int result =solution_2(nums,index+1,preIndex);
            finalRes[index][preIndex+1]=result;
            return result;
        }

    }

    //动态规划
    private int solution_3(int[] nums){

        //1. 设置初始值
        int[][] res = new int[nums.length+1][nums.length+1];

        //2. 逐行填值
        for (int i = nums.length-1; i >= 0; i--) {
            for (int j = 0; j <= nums.length; j++) {
                if (j==0||nums[i]>nums[j-1]){     //j==0代表before=null
                    int result1=res[i+1][i+1]+1;
                    int result2=res[i+1][j];    //不携带
                    res[i][j]=Math.max(result1,result2);
                }else {
                    res[i][j]=res[i+1][j];
                }
            }
        }


        return res[0][0];



    }


}
